package com.programmercarl.tree;

import java.util.*;

/**
 * https://leetcode.cn/problems/convert-bst-to-greater-tree/
 * 把二叉搜索树转换为累加树
 *
 * @author yulongtian
 * @create 2024-12-29 9:27
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Test27 {
    public static void main(String[] args) {
        Test27 test27 = new Test27();
        TreeNode node0 = new TreeNode(0);
        TreeNode node3 = new TreeNode(3);
        TreeNode node2 = new TreeNode(2, null, node3);
        TreeNode node1 = new TreeNode(1, node0, node2);
        TreeNode node5 = new TreeNode(5);
        TreeNode node8 = new TreeNode(8);
        TreeNode node7 = new TreeNode(7, null, node8);
        TreeNode node6 = new TreeNode(6, node5, node7);
        TreeNode root4 = new TreeNode(4, node1, node6);
        List<List<Integer>> lists1 = test27.levelOrder(root4);
        System.out.println(lists1);
        TreeNode treeNode = test27.convertBST(root4);
        List<List<Integer>> lists = test27.levelOrder(treeNode);
        System.out.println(lists);

    }


    /**
     * 右中左
     *
     * @param root
     * @return
     */
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.right = convertBST(root.right);
        root.val += sum;
        sum = root.val;
        root.left = convertBST(root.left);
        return root;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node != null) {
                    temp.add(node.val);
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
            }
            res.add(temp);
        }
        return res;
    }
}
